package demo3;

import java.util.*;

public class Solution {

    //1.剑指 Offer II 069. 山峰数组的顶部
    public int peakIndexInMountainArray(int[] arr) {
        int left = 0;
        int right = arr.length - 1;
        while(left < right) {
            int mid = (left + right) / 2;
            if(arr[mid] < arr[mid + 1]) {
                left = mid + 1;
            } else if(arr[mid] < arr[mid - 1]) {
                right = mid - 1;
            } else {
                return mid;
            }
        }
        return -1;
    }

    //3.剑指 Offer II 004. 只出现一次的数字(位运算)
    public int singleNumber(int[] nums) {
        int[] arr = new int[32];
        for(int num : nums) {
            for(int i = 0; i < 32; i++) {
                if(((num >> i) & 1) == 1) {
                    arr[i]++;
                }
            }
        }
        int sum = 0;
        for(int i = 0; i < 32; i++) {
            if((arr[i] % 3) == 1) {
                sum += (1 << i);
            }
        }
        return sum;
    }

    //4.剑指 Offer II 008. 和大于等于 target 的最短子数组(滑动窗口)
    public int minSubArrayLen(int target, int[] nums) {
        int len = Integer.MAX_VALUE;
        int left = 0;
        int right = 0;
        int sum = 0;
        while(right < nums.length) {
            sum += nums[right];
            while(sum >= target) {
                len = Math.min(len, right - left + 1);
                sum -= nums[left++];
            }
            right++;
        }
        return len == Integer.MAX_VALUE ? 0 : len;
    }

    //5.剑指 Offer II 006. 排序数组中两个数字之和(双指针)
    public int[] twoSum(int[] numbers, int target) {
        int[] ret = new int[2];
        int left = 0;
        int right = numbers.length - 1;
        while(left < right) {
            int sum = numbers[left] + numbers[right];
            if(sum > target) {
                right--;
            } else if(sum < target) {
                left++;
            } else {
                ret[0] = left;
                ret[1] = right;
                break;
            }
        }
        return ret;
    }

    //6.剑指 Offer II 016. 不含重复字符的最长子字符串(滑动窗口)
    public int lengthOfLongestSubstring(String s) {
        List<Character> set = new ArrayList<>();
        int end = 0;
        int maxLen = 0;
        while(end < s.length()) {
            while(set.contains(s.charAt(end))) {
                set.remove(0);
            }
            set.add(s.charAt(end));
            maxLen = Math.max(maxLen, set.size());
            end++;
        }
        return maxLen;
    }

//    //7.剑指 Offer II 005. 单词长度的最大乘积(哈希)
//    public int maxProduct(String[] words) {
//        int maxLen = 0;
//        for(int i = 0; i < words.length; i++) {
//            Set<Character> set = new HashSet<>();
//            int strSize = 0;
//            for(int j = 0; j < words[i].length(); j++) {
//                set.add(words[i].charAt(j));
//                strSize++;
//            }
//            for(int j = i + 1; j < words.length; j++) {
//                int count = 0;
//                for(int k = 0; k < words[j].length(); k++) {
//                    if(set.contains(words[j].charAt(k))) {
//                        count = 0;
//                        break;
//                    } else {
//                        count++;
//                    }
//                }
//                if(count * strSize > maxLen) {
//                    maxLen = count * strSize;
//                }
//            }
//        }
//        return maxLen;
//    }

    //7.剑指 Offer II 005. 单词长度的最大乘积(比特位优化空间 + 位运算优化时间 这可太秀了！)
    public int maxProduct(String[] words) {
        //预计算
        int len = words.length;
        int[] ans = new int[len];
        for(int i = 0; i < len; i++) {
            int bitStr = 0;
            for(char ch : words[i].toCharArray()) {
                bitStr |= 1 << (ch - 'a');
            }
            ans[i] = bitStr;
        }
        //开始比较
        int maxLen = 0;
        for(int i = 0; i < len; i++) {
            for(int j = i + 1; j < len; j++) {
                if((ans[i] & ans[j]) == 0) {
                    maxLen = Math.max(maxLen, words[i].length() * words[j].length());
                }
            }
        }
        return maxLen;
    }

//    private boolean isSameStr(String word1, String word2) {
//        int bitStr1 = 0;
//        int bitStr2 = 0;
//        for(char ch : word1.toCharArray()) {
//            bitStr2 += 1 << (ch - 'a');
//        }
//        for(char ch : word2.toCharArray()) {
//            bitStr2 += 1 << (ch - 'a');
//        }
//        return (bitStr1 & bitStr1) != 0;
//    }

    //8.剑指 Offer II 012. 左右两边子数组的和相等(数学)
    public int pivotIndex(int[] nums) {
        int sum = 0;
        for(int num : nums) {
            sum += num;
        }
        int prev = 0;
        int lSum = 0;
        for(int i = 0; i < nums.length; i++) {
            sum -= nums[i];
            lSum += prev;
            if(sum == lSum) {
                return i;
            }
            prev = nums[i];
        }
        return -1;
    }

    //9.乘积小于 K 的子数组(滑动窗口)
    public int numSubarrayProductLessThanK(int[] nums, int k) {
        if(k <= 1) {
            return 0;
        }
        int left = 0;
        int right = 0;
        int sum = 1;
        int count = 0;
        while(right < nums.length) {
            sum *= nums[right];
            while(sum >= k) {
                sum /= nums[left];
                left++;
            }
            count += right - left + 1;
            right++;
        }
        return count;
    }

    //10.剑指 Offer II 010. 和为 k 的子数组(前缀和)
    public int subarraySum(int[] nums, int k) {
        int len = nums.length;
        int[] sum = new int[len + 1];
        Map<Integer, Integer> map = new HashMap<>();
        //记录前缀和
        for(int i = 1; i <= len; i++) {
            sum[i] = sum[i - 1] + nums[i - 1];
        }
        //统计区间出现次数
        int count = 0;
        for(int i = 0; i <= len; i++) {
            if(map.containsKey(sum[i] - k)) {
                count += map.get(sum[i] - k);
            }
            map.put(sum[i], map.getOrDefault(sum[i], 0) + 1);
        }
        return count;
    }

    //剑指 Offer II 018. 有效的回文()
    public boolean isPalindrome(String s) {
        String str = s.toLowerCase();
        return true;
    }

}



class Main {
    public static void main(String[] args) {
        String str = "A man, a plan, a canal: Panama";
        Solution solution = new Solution();
        solution.isPalindrome(str);
    }
}

//2.剑指 Offer II 041. 滑动窗口的平均值(设计)
class MovingAverage {

    private int sum = 0;
    private int size = 0;
    private Deque<Integer> deque = new ArrayDeque<>();

    /** Initialize your data structure here. */
    public MovingAverage(int size) {
        this.size = size;
    }

    public double next(int val) {
        deque.offerLast(val);
        sum += val;
        if(deque.size() > size){
            sum -= deque.pollFirst();
        }
        return sum * 1.0 / deque.size();
    }

}

